<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>red black tree</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="red-black-tree">red black tree</h1>
<p>links</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=UaLIHuR1t8Q&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=25">https://www.youtube.com/watch?v=UaLIHuR1t8Q&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=25</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/RedBlackTree.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/RedBlackTree.java</a></li>
</ul>
<p>rules</p>
<ul>
<li>root is black</li>
<li>leaf(null node) is black</li>
<li>no red-red relationship</li>
<li>black nodes count the same for all path</li>
</ul>
<h1 id="1-insert">1. insert</h1>
<ol>
<li>if empty tree. create black root node</li>
<li>insert new leaf node as red
<ol>
<li>if its parent is black, then done</li>
<li>if parent is red
<ol>
<li>if parent's sibling is black or absent,  rotate, recolor, done</li>
<li>if parent's sibling is red, then recolor , check again (这种情况比较简单，不需要rotate)</li>
</ol>
</li>
</ol>
</li>
</ol>
<h2 id="11-parents-sibling-is-red">1.1 parent's sibling is red</h2>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred1.png" alt="blackred1.png"></p>
<h2 id="12-parents-sibling-is-black-or-missing">1.2 parent's sibling is black or missing</h2>
<p>rotate, 和AVL tree很相似</p>
<ul>
<li>right rotation</li>
<li>left - right rotation</li>
<li>left rotation</li>
<li>right - left rotation</li>
</ul>
<h3 id="121-right-rotation">1.2.1 right rotation</h3>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred2a.png" alt="blackred2a.png">
<img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred2b.png" alt="blackred2b.png"></p>
<h3 id="122-left---right-rotation">1.2.2 left -&gt; right rotation</h3>
<p>the sibing is missing</p>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred3a.png" alt="blackred3a.png">
<img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred3b.png" alt="blackred3b.png">
<img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred3c.png" alt="blackred3c.png"></p>
<p>the sibing is black</p>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred4a.png" alt="blackred4a.png">
<img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred4b.png" alt="blackred4b.png"></p>
<p>先left rotation</p>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred4c.png" alt="blackred4c.png"></p>
<p>再right rotation一次</p>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred4d.png" alt="blackred4d.png"></p>
<h2 id="right_rotat-code">right_rotat code</h2>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\blackred5.png" alt="blackred5.png"></p>
<h1 id="2-delete">2. delete</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=CTvfzU_uNKE&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=26">https://www.youtube.com/watch?v=CTvfzU_uNKE&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=26</a></li>
</ul>
<ol>
<li>convert to 0 or 1 child case</li>
<li>if node to be deleted is red or child is red then do replace</li>
<li>double black node
<ol>
<li>six cases here</li>
</ol>
</li>
</ol>

    </body>
    </html>